package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;

//------------------
// 解法1
//------------------
//public class Main {
//
//	public static void main(String[] args) {
//
//		Node root = new Node(1);
//		root.left = new Node(2);
//		root.right = new Node(3);
//		root.left.left = new Node(4);
//		root.left.right = new Node(5);
//		root.left.left.left = new Node(6);
//		root.left.left.right = new Node(7);
//		root.left.right.left = new Node(8);
//		root.left.right.right = new Node(9);
//		System.out.println(getLCA(root, root.left.left.left, root.left.right).data);
//	}
//
//	public static Node getLCA(Node node, Node node1, Node node2) {
//
//		Node result = null;
//		if (contains(node, node1, node2)) {
//			result = node;
//			Node temp = getLCA(node.left, node1, node2);
//			if (temp == null) {
//				temp = getLCA(node.right, node1, node2);
//			}
//			result = temp != null ? temp : result;
//		}
//		return result;
//	}
//
//	/**
//	 * 判断node子树是否包含node1和node2
//	 * 
//	 * @param node
//	 * @param node1
//	 * @param node2
//	 * @return
//	 */
//	private static boolean contains(Node node, Node node1, Node node2) {
//
//		return contains(node, node1) && contains(node, node2);
//	}
//
//	private static boolean contains(Node node, Node target) {
//
//		if (node == null) {
//			return false;
//		}
//		if (node == target) {
//			return true;
//		}
//		return contains(node.left, target) || contains(node.right, target);
//	}
//}
//
//class Node {
//
//	public Node left;
//	public Node right;
//	public int data;
//
//	public Node(int data) {
//		this.data = data;
//	}
//}

//--------------------
// 解法2
//--------------------
public class Main {

	public static void main(String[] args) {

		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.left.left.left = new Node(6);
		root.left.left.right = new Node(7);
		root.left.right.left = new Node(8);
		root.left.right.right = new Node(9);
		System.out.println(getLCA(root, root.left.right, root.left));
	}

	public static Integer getLCA(Node node, Node node1, Node node2) {

		List<Integer> list1 = new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		traverse(node, node1, list1);
		traverse(node, node2, list2);
		System.out.println(list1);
		System.out.println(list2);
		int delta = list1.size() - list2.size();
		if (delta < 0) {
			for (int i = 0; i < -delta; i++) {
				list2.remove(0);
			}
		} else if (delta > 0) {
			for (int i = 0; i < delta; i++) {
				list1.remove(0);
			}
		}
		int i = list1.size() - 1;
		while (list1.get(i) != list2.get(i)) {
			list1.remove(i);
			list2.remove(i--);
		}
		return list1.get(i);
	}

	private static boolean traverse(Node node, Node target, List<Integer> list) {

		if (node == null) {
			return false;
		}
		if (node == target) {
			list.add(node.data);
			return true;
		}
		if (traverse(node.left, target, list) || traverse(node.right, target, list)) {
			list.add(node.data);
			return true;
		}
		return false;
	}
}

class Node {

	public Node left;
	public Node right;
	public int data;

	public Node(int data) {
		this.data = data;
	}
}